/**
 * @file     findMedianSortedArrays.js
 * @brief    [4. 寻找两个正序数组的中位数](https://leetcode.cn/problems/median-of-two-sorted-arrays/)
 * @author   Zhu
 * @date     2024-11-29 09:46
 */

/**
 * O(n+m)
 * 双指针合并两个有序数组
 * 不用真实合并，只记录最近的两个值
 * 因为中位数是(m+n)/2位置的值
 * m+n奇数时就是m+n >> 1，可直接返回
 * m+n偶数时高位是m+n >> 1，向前找到低位，求均值即可
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
    let i = 0,
        j = 0;
    const n = nums1.length,
        m = nums2.length;
    const len = n + m;
    const mid = len >> 1; // floor
    let pre, cur;
    const advance1 = () => {
        cur = nums1[i++];
    };
    const advance2 = () => {
        cur = nums2[j++];
    };

    while (i + j <= mid) {
        pre = cur;
        if (i >= n) advance2();
        else if (j >= m) advance1();
        else if (nums1[i] <= nums2[j]) advance1();
        else advance2();
    }

    if (len & 1) {
        // odd
        return cur;
    } else {
        return (pre + cur) / 2;
    }
};

// test case

// 1 2
//-1 3

// 7 8 9
// 1 2 3 6

// 1 2
// 3 4
